package me.mingshan.leetcode;

/**
 * https://leetcode.cn/problems/insert-greatest-common-divisors-in-linked-list/
 * <p>
 * 2807. 在链表中插入最大公约数
 * <p>
 * 给你一个链表的头 head ，每个结点包含一个整数值。
 * <p>
 * 在相邻结点之间，请你插入一个新的结点，结点值为这两个相邻结点值的 最大公约数 。
 * <p>
 * 请你返回插入之后的链表。
 * <p>
 * 两个数的 最大公约数 是可以被两个数字整除的最大正整数。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * <p>
 * 输入：head = [18,6,10,3]
 * 输出：[18,6,6,2,10,1,3]
 * 解释：第一幅图是一开始的链表，第二幅图是插入新结点后的图（蓝色结点为新插入结点）。
 * - 18 和 6 的最大公约数为 6 ，插入第一和第二个结点之间。
 * - 6 和 10 的最大公约数为 2 ，插入第二和第三个结点之间。
 * - 10 和 3 的最大公约数为 1 ，插入第三和第四个结点之间。
 * 所有相邻结点之间都插入完毕，返回链表。
 * 示例 2：
 * <p>
 * <p>
 * <p>
 * 输入：head = [7]
 * 输出：[7]
 * 解释：第一幅图是一开始的链表，第二幅图是插入新结点后的图（蓝色结点为新插入结点）。
 * 没有相邻结点，所以返回初始链表。
 *
 * @author hanjuntao
 * @date 2025/8/1 0001
 */
public class L_2807_insert_greatest_common_divisors_in_linked_list {

    public static void main(String[] args) {
        ListNode head = new ListNode(18);
        head.next = new ListNode(6);
        head.next.next = new ListNode(10);
        head.next.next.next = new ListNode(3);

        ListNode result = insertGreatestCommonDivisors(head);
        ListNode.print(result);

        // 18->6->10->3
        // 18->6->6->10->3
    }

    /**
     * 算法：
     *
     * 1. 创建一个指针，指向当前节点前一个节点
     * 2. 循环链表，计算当前节点和上一个节点的公约数，并生成一个节点，并添加到结果链表中
     *
     * @param head
     * @return
     */
    private static ListNode insertGreatestCommonDivisors(ListNode head) {
        ListNode curr = head;
        ListNode prev = null;

        while (curr != null) {
            if (prev != null) {
                int i = gcd(prev.val, curr.val);
                ListNode node = new ListNode(i);

                prev.next = node;
                node.next = curr;
            }
            prev = curr;
            curr = curr.next;
        }

        return head;
    }

    private static int maxGys(int a, int b) {
        int temp = 1;
        int maxG = 1;

        while (temp <= b && temp <= a) {
            if (a % temp == 0 && b % temp == 0) {
                maxG = temp;
            }
            temp++;
        }

        return maxG;
    }

    /**
     * 用较大数除以较小数，得到余数。
     * 将较小数与余数作为新的一对数，重复上述步骤，直到余数为0。
     * 最后的非零除数即为最大公因数。
     *
     * @param a
     * @param b
     * @return
     */
    private static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}
